package fxy.fxyOffer;

import java.util.Arrays;

public class KNum {
	public int partition(int a[],int low,int high){
		int tmp = a[low];//�ڱ�
		while(low < high){
			while(low < high && a[high] >= tmp){
				high -- ;
			}
			a[low] = a[high];
			while(low < high && a[low] < tmp ){
				low ++;
			}
			a[high] = a[low];
		}
		a[low] = tmp;
		return low;
	}
	public void findK(int a[],int k,int low,int high){
		if(k > a.length || k < 0 || a.length == 0){
			return ;
		}
		int pivot = partition(a, low, high);
		if(pivot < k - 1){
			findK(a,k,pivot + 1,high);
		}else if(pivot > k - 1){
			findK(a ,k , low , pivot - 1);
		}else{
			System.out.println(a[k - 1]);
		}
	}
	public void quickSort(int a[],int low,int high){
		if(a == null || a.length <= 0){
			return;
		}
		if(low <0 || high >= a.length){
			throw new RuntimeException("����Խ��");
		}
		int pivot = partition(a, low, high);
		if(pivot > low){
			quickSort(a, low, pivot - 1);
		}
		if(pivot < high){
			quickSort(a, pivot + 1, high);
		}
	}
	public static void main(String[] args) {
		int a[] = {101,32,345,454,65,101,567,67};
		KNum kNum = new KNum();
		//kNum.quickSort(a, 0, a.length - 1);
		kNum.findK(a, 5, 0, a.length - 1);
		System.err.println(Arrays.toString(a));
	}
}
